'''
https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/description/
'''
from functools import cache
from typing import List

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        total = sum(nums)
        if total % k != 0: return False
        side_len = total // k

        final_status = (1 << n) - 1
        # status: status[i] == 0 表示可以使用，1表示用过了
        # cur_len: 目前做的边长的长度
        # rest: 还剩多少过变成没有做完
        @cache
        def f(status, cur_len):
            if cur_len > side_len: return False
            if cur_len == side_len:
                cur_len = 0
                if status == final_status:
                    return True
            for i in range(n):
                if status >> i & 1: continue
                if f(status | (1 << i), cur_len + nums[i]):
                    return True
            return False

        return f(0, 0)
